package com.tcm.day03;

/**
 * k个一组翻转链表
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/submissions/593772606/?envType=problem-list-v2&envId=linked-list
 */
public class Code05_ReverseKGroup {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = getKGroupNode(start, k);
        if(end == null) {
            return head;
        }

        head = end;
        reverse(start, end);
        ListNode lastEnd = start;

        while(lastEnd.next != null) {
            start = lastEnd.next;
            end = getKGroupNode(start, k);

            if(end == null) {
                return head;
            }

            reverse(start, end);
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

    public ListNode getKGroupNode(ListNode start, int k) {
        while (--k > 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    public void reverse(ListNode start, ListNode end) {
        ListNode tail = end.next;
        ListNode prev = null;
        ListNode cur = start;
        ListNode next = null;

        while (prev != end) {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        start.next = tail;
    }


}
